package cn.zzf.algs.note.exercise.sort;

import cn.zzf.algs.note.base.sort.Sort;
import cn.zzf.algs.note.base.util.SortUtil;

/**
 * 自然的归并排序。编写一个自底向上的归并排序，当需要将两个子数组排序时能够利用数组中已经有序的部分。
 * 首先找到一个有序的子数组（移动指针直到当前元素比上一个元素小为止），然后找到另一个并将它们归并。
 * 根据数组大小和数组中递增子数组的最大长度分析算法的运行时间。
 * @author GaoFeng2017
 * @date 2020/7/23 11:05
 */


public class Ex_2_2_16_NatureBottomUpMergeSort implements Sort {

    private static final int BASE_NUMBER = 2;

    /** 进行归并的数组的最小长度 */
    private static final int MERGE_MIN_LENGTH = 7;

    /** 辅助数组 */
    private Comparable[] auxiliaryElements;

    @Override
    public void sort(Comparable[] elements) {
        this.auxiliaryElements = new Comparable[elements.length];
        this.natureMergeSort(elements);
    }

    private void natureMergeSort(Comparable[] elements) {

        // boolean isFindSecondOrderIndex = false;
        int mid = 0;

        int numberOfSubArrays = 0;


        // 4, 3
        // [512, 116, 53, 368, 534, 531, 374]
        // step-1 false, mid: 0
        // step-2 true, mid: 1
        // step-3 false, mid: 2
        // step-3 true, mid: 2
        for (int i = 0; i < elements.length - 1; i++) {
            if (SortUtil.less(elements[i + 1], elements[i])) {
                // 当最开始的两个子数组合并后，后续的子数组将与第一个合并的数组进行合并，而不是再寻找两个子数组。
                if (mid != i) {
                    this.merge(elements, 0, mid, i);
                }

                // 更新mid的值
                mid = i;
                numberOfSubArrays++;
            }
        }


        // 最后一个区间时有序的，进行整体合并
        if (mid < elements.length - 1) {
            this.merge(elements, 0, mid, elements.length - 1);
            numberOfSubArrays++;
        }

        System.out.println("the number of sub arrays is " + numberOfSubArrays);
        // System.out.println("after nature merge: " + firstOrderIndex + ", " + secondOrderIndex + ", " + Arrays.toString(elements));+ b  k

    }

    private void merge(Comparable[] elements, int beginIndex, int mid, int endIndex) {

        // System.out.println(beginIndex + ", " + mid + ", " + endIndex);

        for (int i = beginIndex; i <= mid; i++) {
            this.auxiliaryElements[i] = elements[i];
        }

        for (int i = mid + 1; i <= endIndex; i++) {
            this.auxiliaryElements[i] = elements[mid + (endIndex - i) + 1];
        }

        int leftIndex = beginIndex;
        int rightIndex = endIndex;
        for (int i = beginIndex; i <= endIndex; i++) {
            if (SortUtil.less(this.auxiliaryElements[rightIndex], this.auxiliaryElements[leftIndex])) {
                elements[i] = this.auxiliaryElements[rightIndex--];
            } else {
                elements[i] = this.auxiliaryElements[leftIndex++];
            }
        }

    }

}
